|
In combinatorial mathematics, a block design is a set together with a family of subsets (repeated subsets are allowed at times) whose members are chosen to satisfy some set of properties that are deemed useful for a particular application. These applications come from many areas, including experimental design, finite geometry, software testing, cryptography, and algebraic geometry. Many variations have been examined, but the most intensely studied are the balanced incomplete block designs (BIBDs or 2-designs) which historically were related to statistical issues in the design of experiments. A block design in which all the blocks have the same size is called ''uniform''. The designs discussed in this article are all uniform. Pairwise balanced designs (PBDs) are examples of block designs that are not necessarily uniform. ==Definition of a BIBD (or 2-design)== Given a finite set ''X'' (of elements called points) and integers ''k'', ''r'', ''λ'' ≥ 1, we define a ''2-design'' (or ''BIBD'', standing for balanced incomplete block design) ''B'' to be a family of ''k''-element subsets of ''X'', called ''blocks'', such that the number ''r'' of blocks containing ''x'' in ''X'' is not dependent on which ''x'' is chosen, and the number ''λ'' of blocks containing given distinct points ''x'' and ''y'' in ''X'' is also independent of the choices. "Family" in the above definition can be replaced by "set" if repeated blocks are not allowed. Designs in which repeated blocks are not allowed are called ''simple''. Here ''v'' (the number of elements of ''X'', called points), ''b'' (the number of blocks), ''k'', ''r'', and λ are the ''parameters'' of the design. (To avoid degenerate examples, it is also assumed that ''v'' > ''k'', so that no block contains all the elements of the set. This is the meaning of "incomplete" in the name of these designs.) In a table: : The design is called a (''v'', ''k'', ''λ'')-design or a (''v'', ''b'', ''r'', ''k'', ''λ'')-design. The parameters are not all independent; ''v'', ''k'', and λ determine ''b'' and ''r'', and not all combinations of ''v'', ''k'', and ''λ'' are possible. The two basic equations connecting these parameters are : : These conditions are not sufficient as, for example, a (43,7,1)-design does not exist.〔Proved by Tarry in 1900 who showed that there was no pair of orthogonal Latin squares of order six. The 2-design with the indicate parameters is equivalent to the existence of five mutually orthogonal Latin squares of order six.〕 The ''order'' of a 2-design is defined to be ''n'' = ''r'' − ''λ''. The complement of a 2-design is obtained by replacing each block with its complement in the point set ''X''. It is also a 2-design and has parameters ''v''′ = ''v'', ''b''′ = ''b'', ''r''′ = ''b'' − ''r'', ''k''′ = ''v'' − ''k'', ''λ''′ = ''λ'' + ''b'' − 2''r''. A 2-design and its complement have the same order. A fundamental theorem, Fisher's inequality, named after the statistician Ronald Fisher, is that ''b'' ≥ ''v'' in any 2-design. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Block design」の詳細全文を読む スポンサード リンク
|